#pragma once

#include <algorithm>
#include <exception>
#include <functional>
#include <initializer_list>
#include <iostream>
#include <istream>
#include <map>
#include <optional>
#include <ostream>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;
using _OptChar = optional<char>;

/****************************************************************
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * * * * * * * * * * * * utils.hpp * * * * * * * * * * * * *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 ****************************************************************
 */
class ParseException : std::exception {
public:
    int linePos;
    int charPos;
    string msg;
    ParseException() = default;
    ParseException(string msg) : msg(msg) {}
    ParseException(int linePos, int charPos, string msg)
        : linePos(linePos), charPos(charPos), msg(msg) {}
};

/****************************************************************
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * * * * * * * * * * * * constants.hpp * * * * * * * * * * * * *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 ****************************************************************
 */

const int __FAKE_END = -1; // make a fake ending char just like '$' in LR(1) parser

// #define __DEBUG
// #define __DEBUG_LV1
// #define __DEBUG_LV2

/****************************************************************
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * * * * * * * * * * * * accept_char.hpp * * * * * * * * * * * * *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 ****************************************************************
 */

// functor to determine if a char is acceptable
class acceptableChars {
private:
    unordered_set<_OptChar> charSet;
    bool exist;

public:
    acceptableChars() : exist(true){};
    acceptableChars(initializer_list<_OptChar> charList, bool exist = true)
        : charSet(charList), exist(exist){};
    acceptableChars(const acceptableChars &s) : charSet(s.charSet), exist(s.exist){};
    acceptableChars &operator=(const acceptableChars &s) {
        charSet = s.charSet;
        exist = s.exist;
        return *this;
    }
    bool match(_OptChar c) const { return !(exist ^ (bool)charSet.count(c)); }
};

/****************************************************************
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * * * * * * * * * * * * fsa_shared_fields.hpp * * * * * * * * * * * * *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 ****************************************************************
 */

class FsaSharedField {
private:
    vector<acceptableChars> _symbols; // charset of the regex
    vector<vector<set<int>>> _states; // [from, symbol, to] matrix

public:
    FsaSharedField(vector<acceptableChars> symbols, vector<vector<set<int>>> states)
        : _symbols(symbols), _states(states){};
    /**
     * Accept a char and transit to another state,
     * @return transited state, return std::nullopt if there is no such transition
     */
    optional<int> transit(int state, char ch) const {
        if (ch == __FAKE_END) {
            return std::nullopt;
        }
        for (int i = 0; i < _symbols.size(); ++i) {
            if (_symbols[i].match(ch)) {
                if (_states.at(state)[i].empty()) {
                    return std::nullopt;
                } else {
                    return *_states.at(state)[i].begin();
                }
            }
        }
        throw ParseException("No such char in the DFA's charset!");
    }
    /**
     * Check if the char should be consumed
     */
    bool advance(int state, char ch) const {
        if (ch == __FAKE_END) {
            return false;
        }
        for (int i = 0; i < _symbols.size(); ++i) {
            if (_symbols[i].match(ch)) {
                return !_states.at(state)[i].empty();
            }
        }
        throw ParseException("No such char in the DFA's charset!");
    }
};

/****************************************************************
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * * * * * * * * * * * * token.hpp * * * * * * * * * * * * *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 ****************************************************************
 */

struct Position {
    int line;
    int col;
    Position() : line(1), col(0) {}
};

class Token {
public:
    string tokenName;
    string word;
    Position startPos;
    Position endPos;
    Token() {
        tokenName = "";
        word = "";
    };
    Token(const string &word, const string &tokenName)
        : word(word), tokenName(tokenName){};
    void clear() {
        tokenName.clear();
        word.clear();
    }
};

/****************************************************************
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * * * * * * * * * * * * my_lexer.hpp * * * * * * * * * * * * *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 ****************************************************************
 */

#define __THROW_INVALID_SYNTAX                                                           \
    std::cerr << "Invalid regex syntax!";                                                \
    throw std::length_error("Invalid regex syntax!");

class MyLexer {
private:
    const FsaSharedField _shared;
    const map<int, const std::string> _acStates;
    const int _BEGIN_STATE;
    enum class State { CHAR, OR, BRACE, BRACE_OR, BRACKET, BRACKET_TO };

public:
    MyLexer(int beginState, FsaSharedField shared, map<int, const string> acStates)
        : _shared(shared), _BEGIN_STATE(beginState), _acStates(acStates) {}

    /**
     * Match the given string
     * @param str the string to match
     * @throw ParseException if syntax error
     * @return matched token name
     */
    vector<Token> lex(const string &str) const {
        stringstream ss;
        ss << str;
        return lex(ss);
    }

    /**
     * Match the given string from stream
     * @param iss input stream
     * @param skipws skip whitespace between tokens
     * @param line line number
     * @return matched token name
     * @throw ParseException if syntax error
     */
    vector<Token> lex(istream &iss, bool skipws = true) const {
        Position curPos;
        vector<Token> ret;
        char ch;
        Token token;
        auto isWS = [](char c) { return c == ' ' || c == '\t' || c == '\n'; };
        optional<int> state = _BEGIN_STATE;
        bool advance = true;
        bool breakwhile = false;
        iss >> std::noskipws;
        while (true) {
            if (advance) {
                if (!(iss >> ch)) {
                    breakwhile = true;
                    ch = __FAKE_END;
                }
                curPos.col++;
            }
            if ((state == _BEGIN_STATE) && skipws && (isWS(ch))) {
                token.startPos = curPos;
                advance = true;
                if (ch == '\n') {
                    curPos.line++;
                    curPos.col = 0;
                }
                if (breakwhile)
                    break;
                continue;
            }
            token.word += ch;
            int oldState = state.value();
            advance = _shared.advance(oldState, ch);
            state = _shared.transit(oldState, ch);
            if (!state) { // no such transition
                auto tokenName = getAcName(oldState);
                if (tokenName) { // is ac state
                    state = _BEGIN_STATE;
                    token.word.pop_back();
                    token.endPos = curPos;
                    token.tokenName = tokenName.value();
                    ret.push_back(token);
                    token.clear();
                } else if ((ch == __FAKE_END) &&
                           (oldState == _BEGIN_STATE)) { // trailing \n
                    break;
                } else { // isn't ac state
                    std::cerr << "Invalid token at line " + std::to_string(curPos.line) +
                                     "[" + std::to_string(curPos.col) + "]: \'" + ch +
                                     "\'\n";
                    throw ParseException(curPos.line, curPos.col, "Invalid token");
                }
            }
            if (breakwhile)
                break;
        } // Main Loop
        return ret;
    }

    std::optional<string> getAcName(int state) const {
        if (_acStates.count(state)) {
            return _acStates.at(state);
        } else {
            return std::nullopt;
        }
    }
};
